#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm> // 用于max
using namespace std;

class ProjectPlanSolution {
public:
    // 项目任务类
    struct ProjectTask {
        int id; // 编号
        int time; // 完成需时
        int indegree; // 入度
        vector<ProjectTask*> nextTasks; // 后置任务
        int startTime; // 最早开始时间
        ProjectTask(int i, int t) : id(i), time(t), indegree(0), startTime(0) {}
    };

    // 任务列表，用数组表示
    vector<ProjectTask*> tasks;

    // 维护当前DFS正在处理中的顶点
    unordered_set<int> process;

    // 返回以起点a出发可以到达的所有邻接点
    vector<int> next(int a) {
        vector<int> nextTasks;
        for (ProjectTask* task : tasks[a]->nextTasks) {
            nextTasks.push_back(task->id);
        }
        return nextTasks;
    }

    // 回溯法寻找有向图中的回退边
    // 如果找到回退边返回true，否则返回false
    bool dfs(int s) {
        // 判断回退边的根据：搜索到一个顶点已经存在于递归搜索当中
        if (process.find(s) != process.end())
            return true;

        // 将当前顶点新加入进dfs搜索顶点
        process.insert(s);

        // 搜索下一个顶点
        for (int t : next(s)) {
            // 递归，而且如果在递归搜索中找到回退边，就可以直接返回
            if (dfs(t))
                return true;
        }

        // 记得把搜索完毕的顶点从搜索列表中移除
        process.erase(s);
        return false;
    }

    // 分支限界法进行任务编排
    void bfs() {
        queue<ProjectTask*> queue;
        for (ProjectTask* task : tasks) {
            if (task->indegree == 0)
                queue.push(task);
        }

        int i = 0;
        while (!queue.empty()) {
            ProjectTask* st = queue.front();
            queue.pop();
            cout << "#" << ++i << " " << st->id << " " << st->startTime << endl;
            for (ProjectTask* t : st->nextTasks) {
                // 更新完成时间及入度，如果入度为0，加入队列
                t->startTime = max(t->startTime, st->startTime + st->time);
                if (--t->indegree == 0)
                    queue.push(t);
            }
        }
    }

    // 项目任务编排
    void projectPlan(int n, const vector<int>& times, const vector<vector<int>>& edges) {
        // 构建图数据结构
        tasks.resize(n);
        for (int i = 0; i < n; i++) {
            tasks[i] = new ProjectTask(i, times[i]);
        }
        for (const auto& ed : edges) {
            int a = ed[0], b = ed[1];
            tasks[a]->nextTasks.push_back(tasks[b]);
            tasks[b]->indegree++;
        }

        // 先执行DFS确认任务的合理性
        for (ProjectTask* task : tasks) {
            if (task->indegree == 0) {
                if (dfs(task->id)) {
                    cout << "任务不合理，存在回退边！" << endl;
                    return;
                }
            }
        }

        // 没问题则执行bfs
        bfs();
    }
};

int main() {
    ProjectPlanSolution sln;
    int n = 10;
    vector<int> times = {0, 2, 2, 1, 4, 5, 1, 6, 4, 0};
    vector<vector<int>> edges = {
        {0, 1}, {0, 4}, {1, 2}, {1, 3}, {2, 5}, {3, 6}, {4, 6}, {5, 7}, {5, 8}, {6, 8}, {7, 9}, {8, 9}
    };
    sln.projectPlan(n, times, edges);
    return 0;
}